1. Field of the Invention
This invention relates to bit adding circuits for summing binary digits, and more particularly, relates to circuits for summing binary partial products resulting from the multiplication of binary operands.
2. Description of the Background Art
There are many possible logical structures for summing the partial product bits resulting from the multiplication of two binary numbers. One known scheme for accomplishing this is a "Wallace" tree that can produce the shortest possible critical path which grows only logarithmically with operand width. See, C.S. Wallace, "A Suggestion for a Fast Multiplier," IEEE Transactions on Electronic Computers, vol. EC-13, pp. 14-17, February, 1964. However, a true Wallace tree requires an irregular structure whose long wire lengths usually add more delay than the Wallace tree might save as compared with a more regular tree structure. These more regular tree structures use pre-wired blocks of adders but the trees still have a total delay that grows only logarithmically with the operarid width. Modern CMOS VLSI implementations of multiplier trees have used structures employing the four-to-two trees and the seven-to-three trees, which are made of combinations of arithmetic adders having four inputs and two outputs, or seven inputs and three outputs, respectively. These multiplier trees are more regular than a Wallace tree but require a greater number of adder delays to sum a large number of partial products. A multiplier tree employing a nine-to-three adder (having nine inputs and three outputs) would be more efficient because it operates in the same number of adder delays as a three-to-two adder, but offers greater uniformity of wiring and simplified circuit layout and design.